#include "../../tools.h"

// 给定区间[n, m]，返回区间内不含 4, 62 的数字个数


int f[8][10];       // 以 j 开头的 i 位数有几个合理数

int work(int x){    // [0, x]
    if(x == 0) return 1;
    int len = (int) log10(x) + 1; // log10(x) + 1 位数
    int mod = 1;
    for(int i = 0; i < len - 1; ++i) mod *= 10;

    int top, pre = 0, sum = 0;
    for(int k = len; k >= 1; --k){
        top = x / mod;
        x %= mod;
        mod /= 10;

        for(int i = 0; i < top; ++i){
            if(pre == 6 && i == 2) continue;
            sum += f[k][i];
        }

        if(k == 1 && top != 4 && (pre != 6 || top != 2))
            ++sum;

        if(pre == 4 || (pre == 6 && top == 2)) break;
        pre = top;
    }
    return sum;
}

int main(int argc, char const *argv[])
{
    f[0][0] = 1; // !!!
    for(int nbit = 1; nbit <= 7; ++nbit){   // 只关心最高位与第二位是否满足，其余的依赖状态转移
        for(int i = 0; i <= 9; ++i){        // 首位数
            if(i == 4) continue;
            for(int j = 0; j <= 9; ++j){    // 第二位数
                if(i == 6 && j == 2) continue;
                f[nbit][i] += f[nbit - 1][j];
            }
        }
    }

    int n = 1, m = 100, ans;
    if(n > m) {cout << 0 << endl; return 0;}
    ans = work(m);      // [0, m]
    ans -= work(n - 1); // [0, n - 1]
    cout << ans << endl;


    // for(int i = 0; i < 8; ++i){
    //     for(int j = 0; j < 8; ++j)
    //         cout << f[i][j] << " ";
    //     cout << endl;
    // }


    return 0;
}


